package 笔试.奇安信;

import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/8/7-14:41
 * @version:1.0
 * @function:
 */
public class 奇安信 {
    public static void main(String[] args) {
        System.out.println(getMaximumResource(new int[][]{{1, 0, 7}, {2, 0, 6}, {3, 4, 5}, {0, 3, 0}, {9, 0, 20}}));
    }
    public static   int TeamNums (int[] height) {
        // write code here
        int count  = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i+1; j>i&&j < height.length; j++) {
                for (int k = j+1; k>j&&k < height.length; k++) {
                    int a = height[i];
                    int b = height[j];
                    int c = height[k];
                    if (a<b&&b<c)count++;
                    if (a>b&&b>c)count++;
                }
            }
        }
        return count;
    }
    public static int getMaximumResource (int[][] grid) {
        // write code here
        int max = 0;
        Stack<Start> starts = new Stack<>();
        for (int i = 0; i < grid.length; i++) {  // 遍历所有的可能起始点
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]!=0){
                    starts.push(new Start(i,j));
                }
            }
        }
        while (!starts.isEmpty()){
            int[][] arr = ArrayCopy(grid);
            Start start = starts.pop();
            max = Math.max(max,find(arr,start.i,start.j));
        }
        return max;
    }
    private static int find(int[][] temp, int i, int j) {
        int sum = temp[i][j];
        int top =0,left=0,right=0,bottom=0;
        temp[i][j] = 0;
        if (i-1>=0&&i-1<temp.length&&temp[i-1][j]!=0){
            int[][] arr = ArrayCopy(temp);
            top = find(arr,i-1,j);
        }
        if (i+1>=0&&i+1<temp.length&&temp[i+1][j]!=0){
            int[][] arr = ArrayCopy(temp);
            bottom = find(arr,i+1,j);
        }
        if (j-1>=0&&j-1<temp[0].length&&temp[i][j-1]!=0){
            int[][] arr = ArrayCopy(temp);
            left = find(arr,i,j-1);
        }
        if (j+1>=0&&j+1<temp[0].length&&temp[i][j+1]!=0){
            int[][] arr = ArrayCopy(temp);
            right = find(arr,i,j+1);
        }
        return sum+Math.max(Math.max(top,bottom),Math.max(left,right));
    }
    private static int[][] ArrayCopy(int[][]temp){
        int[][] arr = new int[temp.length][temp[0].length];
        for (int n = 0; n < temp.length; n++) {  // 遍历所有的可能起始点
            for (int m= 0; m < temp[0].length; m++) {
                arr[n][m] =temp[n][m];
            }
        }
        return arr;
    }
}
class Start{
    int i;
    int j;

    public Start(int i, int j) {
        this.i = i;
        this.j = j;
    }
}
